The demand for networked digital audiovisual systems is expected to grow over the next few years, as business, government and other institutions increasingly turn to digital networks to distribute audiovisual information for education, presentations and reference applications. These customers expect systems that will allow a number of people to be able to view audiovisual information from a server simultaneously, while fully retaining their other network functions. For example, in business computing, most of the major productivity software developers see networked video as an effective means of training and supporting users. Many of these developers have begun including VHS videotapes for training with their software. Now they want to take this a step further by linking the video directly to their software's on-line help resources. Centralizing that support in a video server reduces the cost for customers with many users and ensures that it is properly maintained by the responsible persons.
Networked video presentation systems in business can allow corporate resources, such as sales videos, employee information, and video-based training to be available immediately to all employees from their desks. Similarly, networked video documentation systems will allow institutions of all kinds to maintain multi-user audiovisual databases. One large population of users of such systems are likely to be health care institutions which have extensive audiovisual records. In addition, such databases can be used for on-the-job reference such as revisiting a complex procedure on the manufacturing floor, or creating on-line archive of TV commercials for an advertising agency.
Audiovisual communication including video conferencing, video mail, and collaborative work, is yet another fast growing business application which requires the support of networked video over Local Area Networks.
The characteristics of video traffic differ substantially from those of traditional transactional data traffic to the point that Local Area Networks designed primarily to support data applications are not appropriate to effectively support video services. With data applications, the data rate associated with a traffic source is highly variable; i.e., it exhibits a high peak to average ratio. Accordingly, the design of Local Area Networks aimed at supporting data applications has been based on the principle of bandwidth sharing and statistical time multiplexing. In contrast, the data rate associated with the transmission of a video stream is relatively constant; the precise value depends on the particular encoding scheme used and the image quality desired, but it tends to be much higher than the average rate associated with a transactional data source. In particular, CCITT recommendation H.261 specifies video coding and decoding methods for audiovisual services at the rates of p .times.64 Kbits/s, where p is in the range 1 to 30; the MPEG standard specifies a coded representation that can be used for compressing video sequences to bit rates around 1.5 Mbits/s; Intel's DVI video streams have a data rate of 1.2 Mbits/s or higher depending on the desired quality; the successor to MPEG, known as MPEGII, is being developed to provide a wider range of functionality and image quality than its predecessor at rates in the range of 4 to 9 Mbits/s.
Two important observations can be made. The first is that the volume of bits corresponding to a video segment of useful duration is large. A ten minute DVI video segment corresponds to 90 Mbytes. Ten hours correspond to over 5 Gbytes. Thus video servers for use in systems where shared video information is to be stored must be of relatively high capacity.
The second observation is that the transmission of a video stream of a certain data rate over a Local Area Network requires the provision of a channel of the same data rate on a continuous basis so as to achieve timely delivery of the data. To support the transmission of multiple independent video streams in a local area environment would require a network which can guarantee the bandwidth required for each video stream, and which has an aggregate bandwidth exceeding that required for the maximum configuration expected.
Among the various types of local area networks in existence, the Ethernet type is perhaps the most popular and most widely deployed. It is based on the IEEE 802.3 Standard which allows a number of stations to share a single channel of a given bandwidth. There are several specifications for the physical medium of such a communication channel:
Types 10BASE5 and 10BASE2 specify using coaxial cables in a bus topology with baseband signalling at a data rate of 10 Mb/s; PA1 10BROAD36 specifies using coaxial cable in a tree topology with broadband signalling at a data rate of 10 Mb/s; PA1 Types 1BASE5 and 10BASE-T specify using twisted pairs for connecting stations to a shared hub in a star configuration, with baseband signalling at data rates of 1 Mb/s and 10 Mb/s, respectively. PA1 (a) If the variable maintained by the network interface device is less than a certain limit, the delay .zeta. is selected according to a first basic bandwidth allocation protocol. PA1 (b) If the variable is greater than or equal to the limit, the delay is selected according to a second basic bandwidth allocation protocol.
Star configurations using twisted pairs have become much more popular than bus configurations using coaxial cables. The majority of new installations today use 10BASE-T.
In the baseband case, the most basic network includes several busses having coaxial cables, or several star configurations based on 10BASE-T, or a mixture thereof, connected by repeaters. In such a network, all stations share the same bandwidth (e.g., 10 Mb/s). Packets transmitted by one station are broadcast to all other stations on the network. To offer a total transport capacity beyond the available bandwidth, and thus support higher bandwidth applications and/or interconnect a larger number of stations, many networks of the kind described above (also referred to here as network segments), are interconnected by devices called bridges and routers. Bridges and routers are store-and-forward devices which isolate one network segment from another. Typically, such devices are sufficiently intelligent to forward from one network segment to another only those packets destined to the other segment.
For most data applications which are currently supported by such networks, bandwidth has not imposed a major design constraint on the physical hardware used to implement a network. Instead, as a result of other limitations, networks serving large numbers of stations are typically implemented by interconnecting several network segments. These limitations include the maximum distance that may be covered by the physical medium of the channel and the maximum number of stations that may be connected to a given physical coaxial segment or hub.
Given that the data rates of video streams are on the order of 1 to 2 Mb/s, a 10 Mb/s network segment can simultaneously support only a few streams. Thus, only a few video-capable stations may be active sources or destinations of video streams at the same time. (Note that such a number of stations is smaller than the typical number of stations supported by today's network segments and requires existing networks to incur additional segmentation.) As depicted in FIG. 1, for applications that involve a (video) server 100, the server 100 must be directly accessible from each segment, 110, 120 or 130 and thus must be connected to each segment 110, 120 and 130. The number of segments 110, 120 or 130 to which a server 100 can be connected is limited to the number of Ethernet cards 111, 121 or 131 which fit in the server 100. In this configuration, the server 100 may also serve as a bridge for traffic flowing among the segments 110, 120 or 130. As depicted in FIG. 2, for large numbers of segments 11, 12, a star configuration based on a switching hub 20 is the most appropriate topology. Clearly, the switching hub 20 must have the necessary switching capacity to handle the aggregate traffic which flows among all segments 11 and 12. (The switching hub 20 essentially represents the fusion of all bridges which otherwise would have been used in a mesh configuration, each connecting a few segments, or more typically, a pair of segments). In such a configuration, the video server 18 is connected to the switching hub 20 by means of a link 16 with a bandwidth sufficiently high to support all video streams that the video server 18 is capable of serving. The link 16 may consist of several 10 Mb/s CSMA-CD channels used in parallel, a 100 Mb/s FFDI link or an ATM link with 155 Mb/s or 600 Mb/s, as required. In this case, the video server 18 is accessible to all of the segments 11 and 12 and their associated stations 13. The number of stations 13 that may be connected to each segment 11 or 12 is determined by the bandwidth requirement of each station 13. In the limit, it is possible to connect a single station 13 to each segment 11 or 12, guaranteeing a clear full bandwidth channel to each station 13.
Another major advantage of the switching hub configuration of FIG. 2 stems from the ability to properly handle the integration of different traffic types (video, audio and data) within the switching hub 20 and control the effect of one on another.
In the Local Area Network 10 of FIG. 2 a plurality of stations 13 communicate via a switching hub 20 based on a shared broadcast-type transmission medium 15 having a total bandwidth of W bits/s. Each station 13 is connected, for example, via a repeater 14, to a multiple station shared bus or transmission medium 15 by means of a half-duplex link 17 of rate V bits/s and a port 19. As shown in FIG. 3, each port 19 comprises a transmit FIFO buffer 21 and a receive FIFO buffer 23, of capacity B.sub.t and B.sub.r bits, respectively. The transfer of data from a particular station 13 to a destination device (such as another station 13 or the server 18) takes place in the form of packets of variable size, and follows three steps: the packet is first transmitted by the sending station to its port and is queued in the transmit buffer at that port; when it reaches the head of the queue, it is transmitted over the transmission medium 15 to the port to which the receiving destination device is connected, and is stored in its receive buffer; finally the packet is transmitted from the receiving buffer to the receiving destination device.
In the network 10 of FIG. 2, bandwidth must be allocated in the shared transmission medium 15 to various connections in a fair and efficient manner. A token passing algorithm may be used for allocating bandwidth in the shared transmission medium. A token passing algorithm which allocates resources in the shared transmission medium 15 in a manner so that high priority connections such as a video connections are guaranteed sufficient bandwidth is disclosed in U.S. patent application Ser. No. 07/903,855, filed Jun. 25, 1992, which is now U.S. Pat. No. 5,276,681, and assigned to the assignee hereof. The above-identified patent application is incorporated herein by reference.
The present invention is concerned with the allocation of bandwidth on the channel 17 which connects one or more stations to a port in the switching hub 20. Illustratively, this channel is implemented using a twisted pair physical medium as specified in 10BASE-T. The bandwidth on this channel has to be allocated between the port, which has packets to transmit to the stations, and the stations, which have packets to transmit to each other and to the port. Similarly, the present invention is concerned with the allocation of bandwidth between a bridge, router, or video server and stations on the segments to which such devices are connected. (For convenience, we shall refer to the port, bridge, router, or server as a network interface device.) This invention also applies if the medium 17 is wireless.
The stations transmit packets on the network segment using the IEEE 802.3 CSMA/CD protocol. This protocol operates as follows. Consider that, at some point in time t, a station has a packet ready for transmission. This may be a "new" packet that the station has never previously attempted to transmit, or an "old" packet that has been attempted a certain number of times (i.e., n times, where n.ltoreq.15), but has not been successfully transmitted in any attempts due to collisions with other packets. Thus, the "old" packet has been rescheduled for another attempted transmission at the time t. The station operates as follows:
If the station senses the channel idle at time t, it initiates the transmission of the packet.
If the station senses the channel busy at time t, it monitors the channel until the end-of-carrier appears. Afterwards, following a period of time g called the interframe gap, it initiates the transmission of the packet with probability 1.
One of two outcomes is possible:
i) No collision is detected: The transmission of the packet is completed successfully and, at the end of the packet transmission, the station considers a new packet (if any) for transmission.
ii) A collision is detected: The transmission of the packet is immediately aborted, a jamming signal of duration t.sub.jam is transmitted, and disposition of the transmission of the packet is determined according to the Truncated Exponential Back-off Algorithm. According to the truncated exponential back-off algorithm, if the number of collisions incurred so far by the packet has reached 16, then the station aborts any further attempt to transmit the packet and notifies the upper layer of that event. If the number of thus far incurred collisions n is below 16, then the same packet is rescheduled for transmission following a rescheduling delay .xi.(n) where .xi.=ks, k is an integer selected uniformly in the range [0,2.sup.min{n,10} -1] and s denotes the slot size. (The slot size must be greater than the maximum roundtrip propagation delay .tau. in the network, and has a default value of 51.2 microseconds, or equivalently, 512 bit times.)
Note that the CSMA-CD protocol has been devised for networks comprising a plurality of stations with two main objectives in mind: (i) to give fair access to all stations connected to the network, and (ii) to adapt to the load and to avoid a high rate of repeated collisions by increasing the period of time over which packets are rescheduled. (The number of collisions incurred by a packet is used as an indication of the load on the network.)
To understand the operation of the exponential backoff algorithm, consider the case where a packet to be transmitted from the station suffers its second consecutive collision at time t.sub.2. According to the exponential backoff algorithm, this packet will be scheduled for retransmission at the time t.sub.2 +ks where k is randomly chosen from the range [0,2.sup.2 -1]=[0,1,2,3,]. If, for example, k is chosen to be equal to 2 or 3, then several slots will be open for other stations or network interface devices to transmit one or more packets on the network. Thus, the exponential backoff algorithm automatically provides some bandwidth for other stations or network interface devices. It should be noted that for larger values of n, the size of the integer set from which k is chosen is larger (up to 2.sup.10 -1) and more time slots are available for the station to receive packets from the network interface device.
Now, the transmission of packets containing video data from the network interface device to the station(s) is considered. Such video data must be transmitted in a timely fashion which means that the network interface device must have a guaranteed fraction of the bandwidth of the channel between it and other stations. One possibility is to use the 802.3 protocol at the network interface device. While this protocol can be used at the network interface device for transactional data, it is not suitable for video data. The reason is that the network interface device is not guaranteed a fixed fraction of the bandwidth between the network interface device and the station(s). Instead, the exponential backoff algorithm introduces an element of randomness into the transmission process, i.e., once a packet experiences one or more collisions, it is rescheduled for transmission randomly according to the exponential backoff algorithm. This is not suitable for video data. Another approach is to let the network interface device transmit its packets without incurring any rescheduling delay (i.e., without use of exponential backoff). That is, immediately following an end-of-carrier signal in the channel, the network interface device waits for an interframe gap and then initiates transmission of its packet with probability one. As long as the network interface device has something to transmit, the stations incur a collision at each packet transmission attempt they undertake. Accordingly, should the network interface device remain busy for a long time, the stations will experience repeated collisions and have to give up the transmission of their packets. In short, this scheme gives priority to the network interface device, but provides no guaranteed bandwidth for the station.
It is an object of the present invention, to provide a technique for allocating bandwidth in the channel between a network interface device and stations in a local area network segment. In particular, it is an object of the invention to allocate the bandwidth so that a guaranteed amount of bandwidth is provided to the network interface device without causing the stations to time out. It is a further objective to allocate the bandwidth in the channel between the network interface device and stations so that the network interface device is able to transmit video data to the stations.